/**
 * @file   Graph.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Thu Dec 24 19:38:33 2020
 * 
 * @brief  the class Graph
 * 
 * 
 */

#include <iostream>
#define BLACK 2
#define GRAY 1
#define WHITE 0

template <typename T>
class Graph {
private:
    typedef int Color;
    class Node {
    public:
	T data;
	Node * next;
	int index; //mark the position
	int power; //the power of each edge
	int distance; //evaluate the distance to s
	Color color; //mark the condition
    };
    int max;
    int num;    
    int * matrix;
    Node ** adj_list; //the adjacency list
    Node ** BST(T _x);
public:
    Graph(int n);
    void start_BST(T _x);
    void insert(); //get the graph data and insert the list and matrix
    void matrix_init(); //insert the matrix
    void print(); //print the list and the matrix
    ~Graph();
};

/**
 * @file   Graph.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Wed Dec 30 19:12:11 2020
 * 
 * @brief  BST function
 * 
 * 
 */

template <typename T>
void Graph<T>::start_BST(T _x) {
    Node ** result = BST(_x);
    //this function print the result of BST
    std::cout << std::endl;
    std::cout << "The distance to " << _x << ":" << std::endl;
    for (int i=0;i<num;i++) {
	if (adj_list[i]->distance==max) {
	    std::cout << adj_list[i]->data << " cannot reach!" << std::endl;
	    continue;
	}
	std::cout << adj_list[i]->data << " distance = " << adj_list[i]->distance << ", path: ";
	Node * p = result[i];
	while (p->next!=NULL) {
	    std::cout << p->data << "->";
	    p = p->next;
	}
	std::cout << p->data;
	std::cout << std::endl;
    }
    delete [] result;
}

template <typename T>
typename Graph<T>::Node ** Graph<T>::BST(T _x) {
    //result record the connection of each node
    Node ** result = new Node* [num];
    Node ** Q = new Node* [num];
    Node * min;
    //find the _x
    for (int i=0;i<num;i++) {
	if (adj_list[i]->data==_x) {
	    Q[0] = adj_list[i];
	    Q[0]->distance = 0;
	    Q[0]->color = GRAY;
	    break;
	}
    }
    //init result
    for (int i=0;i<num;i++) {
	result[i] = new Node;
	result[i]->data = adj_list[i]->data;
	result[i]->next = NULL;
    }
    int max = 0;
    int index = 0;
    while (index<num-1) {
	Q[index]->color = BLACK;
	Node * p = Q[index]->next;
	while (p!=NULL) {
	    if (adj_list[p->index]->color==WHITE) {
		max++;
		adj_list[p->index]->distance = Q[index]->distance + 1;
		Q[max] = adj_list[p->index];
		result[p->index]->next = result[Q[index]->index];
	        Q[max]->color = GRAY;
	    }
	    p = p->next;
	}
	Q[index] = NULL;
	index++;
    }
    delete [] Q;
    return result;
}

/**
 * @file   Graph.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Thu Dec 24 23:08:29 2020
 * 
 * @brief  init function
 * 
 * 
 */

template <typename T>
Graph<T>::Graph(int n) {
    max = 0;
    num = n;
    matrix = new int [n*n];
    adj_list = new Node* [n];
    //init the matrix
    for (int i=0;i<n*n;i++) {
	matrix[i] = 0;
    }
}

/**
 * @file   Graph.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Thu Dec 24 23:08:53 2020
 * 
 * @brief  init the matrix
 * 
 * 
 */

template <typename T>
void Graph<T>::matrix_init() {
    //storage the node
    T node[num];
    for (int i=0;i<num;i++) {
	node[i] = adj_list[i]->data;
    }
    for (int i=0;i<num;i++) {
	for (int j=0;j<num;j++) {
	    Node * p = adj_list[i]->next;
	    while (p!=NULL) {
		for (int k=0;k<num;k++) {
		    if (p->data==node[k]) {
			matrix[i*num+k] = 1;
			break;
		    }
		}
		p = p->next;
	    }
	}
    }
}

/**
 * @file   Graph.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Thu Dec 24 23:10:24 2020
 * 
 * @brief  insert function
 * 
 * 
 */

template <typename T>
void Graph<T>::insert() {
    max++;
    //get the data
    T _data[num];
    int _n[num];
    T _link[num*num];
    int index = 0;
    for (int i=0;i<num;i++) {
	std::cin >> _data[i];
	std::cin >> _n[i];
	for (int j=0;j<_n[i];j++) {
	    std::cin >> _link[index];
	    max++;
	    index++;
	}
    }

    //set the list
    index = 0;
    for (int i=0;i<num;i++) {
	adj_list[i] = new Node;
	adj_list[i]->data = _data[i];
	adj_list[i]->index = i;
	adj_list[i]->power = 0;
	adj_list[i]->distance = max;
	adj_list[i]->color = WHITE;
	adj_list[i]->next = NULL;
	Node * p = adj_list[i];
	for (int j=0;j<_n[i];j++) {
	    p->next = new Node;
	    p = p->next;
	    p->distance = max;
	    p->power = 1;
	    p->data = _link[index];
	    for (int k=0;k<num;k++) {
		if (p->data==_data[k]) {
		    p->index = k;
		    break;
		}
	    }
	    p->next = NULL;
	    index++;
	}
    }
    matrix_init();
}

/**
 * @file   Graph.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Thu Dec 24 23:18:51 2020
 * 
 * @brief  init the matrix
 * 
 * 
 */

template <typename T>
void Graph<T>::print() {
    std::cout << "Adjacency list:" << std::endl;
    for (int i=0;i<num;i++) {
	std::cout << adj_list[i]->data << " " << adj_list[i]->index;
	Node * p = adj_list[i]->next;
	while (p!=NULL) {
	    std::cout  << "->" << p->data << " " << p->power;
	    p = p->next;
	}
	std::cout << std::endl;
    }
    std::cout << std::endl;
    std::cout << "Adjacency matrix:" << std::endl;
    std::cout << "  "; 
    for (int i=0;i<num;i++) {
	std::cout << adj_list[i]->data << " ";
    }
    std::cout << std::endl;
    for (int i=0;i<num;i++) {
	std::cout << adj_list[i]->data << " ";
	for (int j=0;j<num;j++) {
	    std::cout << matrix[i*num+j] << " ";
	}
	std::cout << std::endl;
    }
}

/**
 * @file   Graph.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Thu Dec 24 23:18:39 2020
 * 
 * @brief  delete the list and the matrix
 * 
 * 
 */

template <typename T>
Graph<T>::~Graph() {
    for (int i=0;i<num;i++) {
	Node * p = adj_list[i]->next;
	Node * last = p;
	while (p!=NULL) {
	    last = p;
	    p = p->next;
	    delete last;
	}
	delete adj_list[i];
    }
    delete [] matrix;
    delete [] adj_list;
}
